import java.util.ArrayList;

public class RepSel<Type extends Comparable<Type>> {

	private int heapSize;
	private Type[] toSort;
	private Type[] heap;
	private int index;
	private int deadspaceIndex;
	private ArrayList<ArrayList<Type>> runs;
	private ArrayList<Type> currentRun;

	@SuppressWarnings("unchecked")
	public RepSel(int heapSize) {
		this.heapSize = heapSize;
		heap = (Type[]) new Comparable[heapSize];
		runs = new ArrayList<ArrayList<Type>>();
		currentRun = new ArrayList<Type>();
	}

	public void replacementSelection(Type[] toSort) {
		setList(toSort);
		populateHeap();
		while (hasNext()) {
			resetDeadspace();
			buildHeap();
			while (hasRoom() && hasNext()) {
				Type next = getNext();
				sendToRun(heap[0]);
				if (next.compareTo(heap[0]) >= 0) {
					heap[0] = next;
				} else {
					heap[0] = heap[deadspaceIndex];
					heap[deadspaceIndex] = next;
					deadspaceIndex--;
				}
				percDown(0);
			}
		}
		finish();
	}

	private void setList(Type[] toSort) {
		this.toSort = toSort;
	}

	private void populateHeap() {
		while (index < heapSize) {
			heap[index] = getNext();
		}
	}

	public void resetDeadspace() {
		deadspaceIndex = heapSize - 1;
	}

	private int leftChild(int i) {
		return (2 * i) + 1;
	}

	private void finish() {
		int lastDeadspaceIndex = deadspaceIndex +1;
		while(deadspaceIndex > -1) {
			sendToRun(removeMin());
		}
		processOldRun();
		
		@SuppressWarnings("unchecked")
		Type[] newSort = (Type[]) new Comparable[heapSize - lastDeadspaceIndex];
		
		for(int i = 0; i < newSort.length; i++) {
			newSort[i] = heap[lastDeadspaceIndex + i];
		}
		
		heap = newSort;
		deadspaceIndex = heap.length -1;
		buildHeap();
		while(deadspaceIndex > -1) {
			sendToRun(removeMin());
		}
		
		processOldRun();
	}

	private void buildHeap() {
		for (int i = ((deadspaceIndex - 1) / 2); i >= 0; i--) {
			percDown(i);
		}

		processOldRun();
	}
	
	private Type removeMin() {
		Type temp = heap[0];
		heap[0] = heap[deadspaceIndex];
		deadspaceIndex--;
		percDown(0);
		return temp;
	}

	private void percDown(int i) {
		int child = 0;
		Type tmp = null;

		for (tmp = heap[i]; leftChild(i) <= deadspaceIndex; i = child) {
			child = leftChild(i);
			if (child < deadspaceIndex
					&& heap[child].compareTo(heap[child + 1]) > 0) {
				child++;
			}
			if (tmp.compareTo(heap[child]) > 0) {
				heap[i] = heap[child];
			} else {
				break;
			}
		}
		heap[i] = tmp;
	}

	private void processOldRun() {
		if (currentRun == null) {
			currentRun = new ArrayList<Type>();
		} else {
			ArrayList<Type> toAdd = currentRun;
			if (toAdd.size() > 1) {
				runs.add(toAdd);
			}
			currentRun = new ArrayList<Type>();
		}
	}

	private Type getNext() {
		return toSort[index++];
	}

	private boolean hasNext() {
		return index < toSort.length;
	}

	private boolean hasRoom() {
		return deadspaceIndex > -1;
	}

	private void sendToRun(Type toSend) {
		currentRun.add(toSend);
	}

	public ArrayList<ArrayList<Type>> getRuns() {
		return runs;
	}

}